Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Quiz
Question 1
Which of the following statements is true about time complexity analysis?
A
Time complexity is a measure of the number of operations an algorithm performs relative to the input size.
B
Time complexity helps measure the space used by an algorithm.
C
Time complexity analysis is not useful for comparing algorithms.
D
Time complexity is independent of the input size.
Question 2
What is the time complexity of the following code?
public void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {  // Loop 1
        for (int j = i + 1; j < arr.length; j++) {  // Loop 2
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}
A
O(n)
B
O(n2)
C
O(log n)
D
O(n3)
Question 3
What is the time complexity of the following code snippet?
public void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        System.out.println(arr[i]);
    }
}
A
O(n)
B
O(n2)
C
O(log n)
D
O(1)
Question 4
Which of the following best describes Big-O notation?
A
It gives the exact runtime of an algorithm.
B
It measures the algorithm's best-case scenario.
C
It provides the upper bound of an algorithm's growth rate.
D
It is used for measuring space complexity only.
Question 5
Analyze the time complexity of the following code:
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}
A
O(n)
B
O(n2)
C
O(log n)
D
O(n log n)
Question 6
What is the time complexity of the following code snippet?
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, dp[i]);
    }
    return max;
}
A
O(n)
B
O(n log n)
C
O(2n)
D
O(n2)
Question 7
What is the time complexity of the following code?
public int matrixChainOrder(int[] p) {
    int n = p.length;
    int[][] dp = new int[n][n];

    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k <= j - 1; k++) {
                int q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                dp[i][j] = Math.min(dp[i][j], q);
            }
        }
    }
    return dp[1][n - 1];
}
A
O(n)
B
O(n2)
C
O(n3)
D
O(2n)
Question 8
What is the time complexity of the following code?
public int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;

    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}
A
O(n)
B
O(n2)
C
O(n log n)
D
O(2n)
Question 9
Analyze the time complexity of the following code:
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
A
O(n)
B
O(amount * coins.length)
C
O(n2)
D
O(2n)
Quadratic Time: O(n²)
Understanding Space Complexity
Mark as Completed

On this page